#include <bits/stdc++.h>

using namespace std;

struct SkiplistNode
{
    int _val;
    vector<SkiplistNode *> _vNext;
    SkiplistNode(int val, int size)
        : _val(val), _vNext(size, nullptr)
    {
    }
};

class Skiplist
{
public:
    Skiplist()
    {
        srand(time(nullptr));
        _Head = new SkiplistNode(-1, 1);
    }

    bool search(int target)
    {
        int level = _Head->_vNext.size() - 1;
        SkiplistNode *cur = _Head;
        while (level >= 0)
        {
            if (!cur->_vNext[level] || cur->_vNext[level]->_val > target)
            {
                --level;
            }
            else if (cur->_vNext[level]->_val < target)
            {
                cur = cur->_vNext[level];
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    vector<SkiplistNode *> preTrace(int target)
    {
        int level = _Head->_vNext.size() - 1;
        vector<SkiplistNode *> ret(level + 1, nullptr);
        SkiplistNode *cur = _Head;
        while (level >= 0)
        {
            if (!cur->_vNext[level] || cur->_vNext[level]->_val >= target)
            {
                ret[level] = cur;
                --level;
            }
            else
            {
                cur = cur->_vNext[level];
            }
        }
        return ret;
    }

    void add(int num)
    {
        auto pre = preTrace(num);
        // 随机出层数
        int n = Random();
        SkiplistNode *newNode = new SkiplistNode(num, n);
        if (n > _Head->_vNext.size())
        {
            _Head->_vNext.resize(n, nullptr);
            pre.resize(n, _Head);
        }
        for (size_t i = 0; i < n; ++i)
        {
            newNode->_vNext[i] = pre[i]->_vNext[i];
            pre[i]->_vNext[i] = newNode;
        }
    }

    bool erase(int num)
    {
        auto pre = preTrace(num);
        SkiplistNode *cur = pre[0]->_vNext[0];
        if (cur == nullptr || cur->_val != num)
        {
            return false;
        }
        for (int i = 0; i < cur->_vNext.size(); ++i)
        {
            pre[i]->_vNext[i] = cur->_vNext[i];
        }
        delete cur;
        return true;
    }

    int Random()
    {
        size_t level = 1;
        while (rand() < RAND_MAX * _p && level < _MaxLevel)
        {
            ++level;
        }
        return level;
    }

private:
    SkiplistNode *_Head;
    double _p = 0.25;
    int _MaxLevel = 16;
};
/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */